1. Technical Field
The invention is related to a system for compression of images that have masked or “don't care” regions which are delineated by a binary image mask, and in particular, to a system for encoding and decoding of an image using wavelet transforms which are functions of the binary mask.
2. Related Art
There are several existing schemes for compressing masked images. In general, a masked image is an image having holes or missing pixels which are defined by a binary image or “mask.” Such masked images are often used with clipart or “cut-outs”, where images of arbitrary shapes are used for pasting onto other images. In addition, another type of masked image is frequently seen with general composite documents, where text or lines are superimposed on an image. Such text and lines typically have relatively high frequencies relative to the underlying image. Consequently, existing image compression schemes typically achieve poor compression of such composite images.
The basic problem in compressing masked images is to maximize image compression given an input image that is to be compressed, along with a mask which indicates for each pixel in the input image whether the pixel is visible, i.e., not covered by the mask, or whether it is not visible, i.e., covered by the mask.
Conventional solutions to this basic compression problem typically fall into two categories. The first is to fill the data that is masked with “hallucinated” data (i.e., data used to fill don't care regions of an image to assist in compressing the image), and then use a regular image compression technique. The simplest way to fill the missing data is to fill it with the image average. However, schemes based on such filling techniques are not very efficient because they tend to creates sharp discontinuities at the mask boundaries. Further, such discontinuities at the mask boundaries not only increase the required bit rate for a given peak signal-to-noise ratio (PSNR), but also produce noticeable ringing near the mask boundaries.
Related schemes color each pixel with the color of the closest non-masked pixel. Standard morphology algorithms allow such color filling to be performed with only two passes over all the pixels, leading to “Voronoi-filled” regions under the mask. Next, the reconstructed image is low-passed and then the known pixels are restored to their correct values. However, if the lowpass filter cutoff frequency is too low, discontinuities and ringing at the mask boundaries are again seen, while if the cutoff frequency is too high, sharp edges of the Voronoi diagrams will consume too many bits, thereby resulting in reduced compression efficiency. However, advantages to this approach include the fact that it is very simple to implement and computationally efficient.
Another conventional approach to the problem is to use projection onto convex set (POCS). This is the approach used in systems such as the well known “DjVu” scheme. In general, the DjVu scheme considers two convex sets: a set of images that matches the input on the visible pixels, and a set of images that have certain wavelet coefficients set to zero (e.g. all high-frequency coefficients beyond a certain resolution level). By alternating projection on those two sets, one can find an image that agrees with the visible pixels, and which compresses well because it has many zero wavelet coefficients.
The second category of solutions to the basic compression problem noted above use wavelet transforms designed explicitly for irregular grids. Given a masked image, the set of unmasked pixels can be considered as an irregular sampling grid because a number of pixels in the input image are masked, and thus not sampled for compression. However, conventional techniques based on irregular grids are directed towards smooth data interpolation rather than maximization of compression performance.
Therefore, what is needed is a system and method for maximizing compression performance for masked images while avoiding color filling of masked pixels which can result in discontinuities and ringing at the mask boundaries and reduced compression efficiency.